package com.example.demo5;

/**
 * 案例五：二分查找的应用(力扣网)
 */
public class Test {
    public static void main(String[] args) {
        // 需求：给你一个按照非递减顺序排列的整数数组nums,和一个目标值 target,请你找出给定目标值在数组中的开始位置和结束位置
        // 如果数组中不存在目标值 target,返回 [-1, -1]   注意：必须确保程序的时间复杂度是o(log2n),否则不给分数
        // 例如：
        // 数组 nums = [5,7,7,8,8,10], target = 8 得到结果是：[3,4]
        // 数组：nums = [5,7,7,8,8,10], target = 6 得到结果是：[-1,-1]
        // 数组：nums = [], target = 0 得到结果是：[-1,-1]
        int[] nums = {5, 7, 7, 7, 8, 8, 9};
        int leftIndex = getLeftIndex(nums, 7);
        int rightIndex = getRightIndex(nums, 7);
        System.out.println("[" + leftIndex + "," + rightIndex + "]");
    }

    // 先找左边的7
    public static int getLeftIndex(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rs = -1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (target < nums[middle]) {
                right = middle - 1;
            } else if (target > nums[middle]) {
                left = middle + 1;
            } else {
                rs = middle;
                // 继续二分在往左边找找看
                right = middle - 1;
            }
        }
        return rs;
    }

    public static int getRightIndex(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rs = -1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (target < nums[middle]) {
                right = middle - 1;
            } else if (target > nums[middle]) {
                left = middle + 1;
            } else {
                rs = middle;
                // 继续二分在往右边找找看
                left = middle + 1;
            }
        }
        return rs;
    }
}
